﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using SimpleIR;
using System.Diagnostics.Contracts;

namespace RgnAnalyzer.Domain
{
	/// <summary>
	/// This class is to support normalization of the memory locations.
	/// In particular it is used for representing equivalence classes of locations and associated information.
	/// </summary>
	internal class AMemEqPartition
	{
		/// <summary>
		/// Map from the eq class idsntifiers to the equivalence classes.
		/// </summary>
		private readonly Dictionary<int, AMemPartEqClass> m_IDToClassMap;

		/// <summary>
		/// Map from the locations to the equivalence classes that contain them.
		/// </summary>
		private readonly Dictionary<ALocation, AMemPartEqClass> m_locToClassMap;

		/// <summary>
		/// The first model that these locations may have come from.
		/// </summary>
		private readonly AProgramMemory m_model1;

		/// <summary>
		/// The second model that these locations may have come from.
		/// </summary>
		private readonly AProgramMemory m_model2;

		private void CheckConsistent()
		{
#if DEBUG
			foreach(KeyValuePair<int, AMemPartEqClass> idm in this.m_IDToClassMap)
				Contract.Assert(idm.Key == idm.Value.PartitionID);

			foreach(KeyValuePair<ALocation, AMemPartEqClass> idm in this.m_locToClassMap)
			{
				Contract.Assert(idm.Value.PartitionElems.Contains(idm.Key));

				foreach(ALocation nn in idm.Value.PartitionElems)
					Contract.Assert(this.m_locToClassMap[nn] == idm.Value);
			}
#endif
		}

		private ALocation LookupTargetLocation(ALocation sourceloc, int targetid)
		{
			Contract.Requires(sourceloc != null);

			if(this.m_model2 == null)
				return this.m_model1.Memory[targetid];
			else
			{
				if(sourceloc.Address < this.m_model1.Memory.Count && sourceloc == this.m_model1.Memory[sourceloc.Address])
					return this.m_model1.Memory[targetid];
				else
					return this.m_model2.Memory[targetid];
			}
		}

		internal Dictionary<int, AMemPartEqClass> PartIDToEqClassMap
		{
			get
			{
				Contract.Ensures(Contract.Result<Dictionary<int, AMemPartEqClass>>() != null);

				return this.m_IDToClassMap;
			}
		}

		/// <summary>
		/// If we want to compute the congruence closure for a single model use this.
		/// </summary>
		internal AMemEqPartition(AProgramMemory m)
		{
			Contract.Requires(m != null);

			this.m_IDToClassMap = new Dictionary<int, AMemPartEqClass>();
			this.m_locToClassMap = new Dictionary<ALocation, AMemPartEqClass>();
			this.m_model1 = m;
			this.m_model2 = null;
		}

		/// <summary>
		/// If we want to compute the congruence closure of 2 models use this.
		/// </summary>
		internal AMemEqPartition(AProgramMemory m1, AProgramMemory m2)
		{
			Contract.Requires(m1 != null);
			Contract.Requires(m2 != null);

			this.m_IDToClassMap = new Dictionary<int, AMemPartEqClass>();
			this.m_locToClassMap = new Dictionary<ALocation, AMemPartEqClass>();
			this.m_model1 = m1;
			this.m_model2 = m2;
		}

		/// <summary>
		/// Add an equivalence class for the given node.
		/// </summary>
		internal void AddEquivClassForLocation(ALocation l)
		{
			Contract.Requires(l != null);

			AMemPartEqClass leq = new AMemPartEqClass(this.m_locToClassMap.Count, l);
			this.m_IDToClassMap.Add(leq.PartitionID, leq);
			this.m_locToClassMap.Add(l, leq);
		}

		/// <summary>
		/// Set this partition as containing the home location for a variable or static field.
		/// </summary>
		internal void SetAsNameHomeLocation(IRRootIdentifier r, ALocation l)
		{
			Contract.Requires(r != null);
			Contract.Requires(l != null);

			AMemPartEqClass pp = this.m_locToClassMap[l];
			pp.SetAsNameHomeLocation(r);
		}

		/// <summary>
		/// Set this partition as containing the target of an external reference.
		/// </summary>
		internal void AddAsTargetOfExternalRef(AExternalRef eref, ALocation l)
		{
			Contract.Requires(eref != null);
			Contract.Requires(l != null);

			AMemPartEqClass pp = this.m_locToClassMap[l];
			pp.AddAsTargetOfExternalRef(eref);
		}

		/// <summary>
		/// Set this partition as containing the target of a variable or static field.
		/// </summary>
		internal void AddAsTargetOfVarOrStatic(IRRootIdentifier r, ALocation l)
		{
			Contract.Requires(r != null);
			Contract.Requires(l != null);

			AMemPartEqClass pp = this.m_locToClassMap[l];
			pp.AddAsTargetOfVarOrStatic(r);
		}

		/// <summary>
		/// Set this partition as containing the target of an eval stack location.
		/// </summary>
		internal void AddAsTargetOfStackLoc(int spos, IRBasicAccessPath accp, ALocation l)
		{
			Contract.Requires(accp != null);
			Contract.Requires(l != null);

			AMemPartEqClass pp = this.m_locToClassMap[l];
			pp.AddAsTargetOfStackLoc(spos, accp);
		}

		/// <summary>
		/// Set this partition as containing a location that refers to a location in the given partition from a pointer at the given access path.
		/// </summary>
		internal void AddMemorySuccessorAndPredecessor(ALocation source, IRBasicAccessPath pth, ALocation trgt)
		{
			Contract.Requires(source != null);
			Contract.Requires(trgt != null);
			Contract.Requires(source != trgt);

			AMemPartEqClass pps = this.m_locToClassMap[source];
			AMemPartEqClass ppt = this.m_locToClassMap[trgt];
			Contract.Assert(pps != ppt);

			ppt.AddMemoryPredecessor(pps.PartitionID, pth);
		}

		/// <summary>
		/// Take 2 locations that should be in the same equivalence class and merge things as needed.
		/// </summary>
		internal void MergeEqClassesForLocations(ALocation l1, ALocation l2)
		{
			Contract.Requires(l1 != null);
			Contract.Requires(l2 != null);

			AMemPartEqClass cl1 = this.m_locToClassMap[l1];
			AMemPartEqClass cl2 = this.m_locToClassMap[l2];

			this.MergeEqClasses(cl1, cl2);
		}

		/// <summary>
		/// As needed merge the given equivalence partitions.
		/// </summary>
		internal void MergeEqClasses(AMemPartEqClass cl1, AMemPartEqClass cl2)
		{
			Contract.Requires(cl1 != null);
			Contract.Requires(cl2 != null);

			if(cl1 == cl2)
				return;

			//fixup the target source info for reference to cl2
			this.m_IDToClassMap.Remove(cl2.PartitionID);
			for(int i = 0; i < cl2.PartitionElems.Count; ++i)
				this.m_locToClassMap[cl2.PartitionElems[i]] = cl1;

			HashSet<AMemPartEqClass> succparts = new HashSet<AMemPartEqClass>();
			for(int i = 0; i < cl2.PartitionElems.Count; ++i)
			{
				ALocation sl = cl2.PartitionElems[i];
				IEnumerator<ATrgtEnum> trgenum = sl.GetTargetEnum();
				while(trgenum.MoveNext())
				{
					ATrgtEnum tte = trgenum.Current;
					ALocation tl = this.LookupTargetLocation(sl, tte.TrgtAddress);
					AMemPartEqClass pq = this.m_locToClassMap[tl];
					if(pq != cl2)
						succparts.Add(pq);
				}
			}

			foreach(AMemPartEqClass succ in succparts)
				succ.UpdatePredInfoOnMerge(cl2.PartitionID, cl1.PartitionID);

			//merge the partitions
			cl1.MergeOtherClassIntoThis(cl2);
		}

		/// <summary>
		/// When we are computing the summary abstract memory for 2 memories <c>m1</c> and <c>m2</c> use this to fill the maps (and the partition array) from 
		/// node IDs in each of the memories into the partition that they belong to.
		/// 
		/// Watch out this is a bit wild as it implicitly builds the maps in a way that deals with the cartisean product of the partitions \cross the types in each partition!!!!
		/// </summary>
		internal AMemPartEqClass[] FillNodeIDToEquivIDMappingAndArray(AProgramMemory m1, Dictionary<int, int> nodetonewidmap1, AProgramMemory m2, Dictionary<int, int> nodetonewidmap2)
		{
			Contract.Requires(m1 != null && (!m1.IsInfeasable));
			Contract.Requires(nodetonewidmap1 != null);
			Contract.Requires(m2 != null && (!m2.IsInfeasable));
			Contract.Requires(nodetonewidmap2 != null);
			Contract.Ensures(Contract.Result<AMemPartEqClass[]>() != null);

			AMemPartEqClass[] res = new AMemPartEqClass[this.m_IDToClassMap.Count];
			int pctr = 0;
			int rpctr = 0;
			
			foreach(KeyValuePair<int, AMemPartEqClass> kvp in this.m_IDToClassMap)
			{
				res[pctr] = kvp.Value;

				for(int j = 0; j < kvp.Value.PartitionTypes.Count; ++j)
				{
					for(int i = 0; i < kvp.Value.PartitionElems.Count; ++i)
					{
						ALocation ll = kvp.Value.PartitionElems[i];
						if(ll.LocationType == kvp.Value.PartitionTypes[j])
						{
							if(ll.Address < m1.Memory.Count && ll == m1.Memory[ll.Address])
								nodetonewidmap1.Add(ll.Address, rpctr);
							else
								nodetonewidmap2.Add(ll.Address, rpctr);
						}
					}

					++rpctr;
				}

				++pctr;
			}

			return res;
		}

		/// <summary>
		/// Takes a list if the nodes that are roots and computes the congruence closure starting from them.
		/// </summary>
		internal void ComputeCongruenceClosure(List<Tuple<IRBasicAccessPath, ALocation>>[] evalstackedgesets, Dictionary<IRRootIdentifier, List<ALocation>> varandstaticnametargets,
			Dictionary<AExternalRef, List<ALocation>> externalrefsets, List<ALocation> roots, HashSet<AHomeLocation> statichomelocs, bool ignoreidentitystate)
		{
			Contract.Requires(evalstackedgesets != null);
			Contract.Requires(varandstaticnametargets != null);
			Contract.Requires(externalrefsets != null);
			Contract.Requires(roots != null);

			int occsize = Int32.MaxValue;

			//merge all the var and static name home locations (these are always the strongest so we never need to check before mergeing on them)
			foreach(List<ALocation> tl in varandstaticnametargets.Values)
			{
				if(tl.Count >= 2)
				{
					ALocation tnbase = tl[0];
					for(int j = 1; j < tl.Count; ++j)
					{
						ALocation tnn = tl[j];
						this.MergeEqClassesForLocations(tnbase, tnn);
					}
				}
			}

			//merge all the static variable targets
			foreach(ALocation ll in statichomelocs)
			{
				AMemPartEqClass teqc = this.m_locToClassMap[ll];
				HashSet<ALocation> tpltm = new HashSet<ALocation>();

				for(int i = 0; i < teqc.PartitionElems.Count; ++i)
				{
					IEnumerator<ATrgtEnum> trgtenum = teqc.PartitionElems[i].GetTargetEnum();
					while(trgtenum.MoveNext())
					{
						ATrgtEnum tte = trgtenum.Current;
						ALocation trgtl = this.LookupTargetLocation(teqc.PartitionElems[i], tte.TrgtAddress);
						tpltm.Add(trgtl);
					}
				}

				foreach(ALocation pn1 in tpltm)
				{
					foreach(ALocation pn2 in tpltm)
						this.MergeEqClassesForLocations(pn1, pn2);
				}
			}

			do
			{
				occsize = this.m_IDToClassMap.Count;

				List<TargetLocationAndPathPair> namedsourceandtrgtnodeid = new List<TargetLocationAndPathPair>();

				//merge all the external references
				foreach(List<ALocation> tl in externalrefsets.Values)
				{
					if(tl.Count >= 2)
					{
						for(int j = 0; j < tl.Count; ++j)
						{
							ALocation tll = tl[j];
							TargetLocationAndPathPair sltp = new TargetLocationAndPathPair(IRBasicAccessPath.EmptyAccessPath, tll);
							namedsourceandtrgtnodeid.Add(sltp);
						}

						namedsourceandtrgtnodeid.Sort();
						this.ComputeEquivDueToPred(namedsourceandtrgtnodeid, ignoreidentitystate);

						namedsourceandtrgtnodeid.Clear();
					}
				}

				//merge all the eval stack targets
				for(int i = 0; i < evalstackedgesets.Length; ++i)
				{
					if(evalstackedgesets[i].Count >= 2)
					{
						for(int j = 0; j < evalstackedgesets[i].Count; ++j)
						{
							IRBasicAccessPath accp = evalstackedgesets[i][j].Item1;
							ALocation tll = evalstackedgesets[i][j].Item2;
							TargetLocationAndPathPair sltp = new TargetLocationAndPathPair(accp, tll);
							namedsourceandtrgtnodeid.Add(sltp);
						}

						namedsourceandtrgtnodeid.Sort();
						this.ComputeEquivDueToPred(namedsourceandtrgtnodeid, ignoreidentitystate);

						namedsourceandtrgtnodeid.Clear();
					}
				}

				//now process all the node locations
				//first compute a top down order to process the equivalence classes in
				List<AMemPartEqClass> cll = new List<AMemPartEqClass>();
				this.TopoSort(cll, roots);
				Queue<AMemPartEqClass> toproc = new Queue<AMemPartEqClass>(cll);

				HashSet<AMemPartEqClass> receq = new HashSet<AMemPartEqClass>();
				List<TargetLocationAndPathPair> refsourceandtrgtnodeid = new List<TargetLocationAndPathPair>();

				//now iterate through the worklist processing nodes until the list is empty
				while(toproc.Count != 0)
				{
					AMemPartEqClass ncl = toproc.Dequeue();
					if(!this.m_IDToClassMap.ContainsKey(ncl.PartitionID))
						continue;

					ncl.Color = AMemPartEqClass.VisitColor.White;
					bool addsucc = false;

					//check for recursive structures starting from ncl
					receq.Clear();
					if(!ncl.IsHomeLocation)
						this.ComputeEquivDueToRecStructure(ncl, receq);

					//merge all recursive structures
					if(receq.Count >= 2)
					{
						List<AMemPartEqClass> tcl = new List<AMemPartEqClass>(receq);
						for(int i = 1; i < tcl.Count; ++i)
							this.MergeEqClasses(tcl[0], tcl[i]);
						addsucc = true;
					}

					for(int tpi = 0; tpi < ncl.PartitionTypes.Count; ++tpi)
					{
						refsourceandtrgtnodeid.Clear();

						for(int i = 0; i < ncl.PartitionElems.Count; ++i)
						{
							ALocation ll = ncl.PartitionElems[i];
							if(ll.LocationType != ncl.PartitionTypes[tpi])
								continue;

							IEnumerator<ATrgtEnum> trgenum = ll.GetTargetEnum();
							while(trgenum.MoveNext())
							{
								ATrgtEnum tee = trgenum.Current;
								ALocation tl = this.LookupTargetLocation(ll, tee.TrgtAddress);
								AMemPartEqClass peq = this.m_locToClassMap[tl];

								if(peq != ncl)
									refsourceandtrgtnodeid.Add(new TargetLocationAndPathPair(tee.BAPPath, tl));
							}
						}

						//check for pred equivalent structures
						refsourceandtrgtnodeid.Sort();
						addsucc |= this.ComputeEquivDueToPred(refsourceandtrgtnodeid, ignoreidentitystate);
					}

					//if merges occoured add successors as needed
					if(addsucc)
						this.AddSuccssorsAsNeeded(ncl, toproc);
				}
			}
			while(occsize != this.m_IDToClassMap.Count);

			this.CheckConsistent();
		}

		/// <summary>
		/// Using <c>src</c> as the root for the recursive structure find the maximal extent of it, putting it into <c>recequiv</c>.
		/// </summary>
		private void ComputeEquivDueToRecStructure(AMemPartEqClass src, HashSet<AMemPartEqClass> recequiv)
		{
			Contract.Requires(src != null);
			Contract.Requires(recequiv != null);

			Queue<AMemPartEqClass> ntpc = new Queue<AMemPartEqClass>();
			ntpc.Enqueue(src);
			recequiv.Add(src);

			while(ntpc.Count != 0)
			{
				AMemPartEqClass neq = ntpc.Dequeue();
				for(int i = 0; i < neq.PartitionElems.Count; ++i)
				{
					ALocation ll = neq.PartitionElems[i];
					IEnumerator<ATrgtEnum> trgtenum = ll.GetTargetEnum();
					while(trgtenum.MoveNext())
					{
						ATrgtEnum tee = trgtenum.Current;
						ALocation qqtn = this.LookupTargetLocation(ll, tee.TrgtAddress);
						AMemPartEqClass qqclass = this.m_locToClassMap[qqtn];

						bool recw = AMemPartEqClass.CheckEquivPartitionsRecEquiv(neq, qqclass);
						bool notinset = !recequiv.Contains(qqclass);
						if(recw & notinset)
						{
							recequiv.Add(qqclass);
							ntpc.Enqueue(qqclass);
						}
					}
				}
			}
		}

		/// <summary>
		/// Using <c>src</c> as the root find and merge all the equivalence classes that are predecessor equivalent due to out edges from it.
		/// </summary>
		private bool ComputeEquivDueToPred(List<TargetLocationAndPathPair> refsourceandtrgtnodeid, bool ignoreidentitystate)
		{
			Contract.Requires(refsourceandtrgtnodeid != null);

			bool succproc = false;

			//now compute the equiv classes
			int blocksl = 0;
			while(blocksl < refsourceandtrgtnodeid.Count)
			{
				IRBasicAccessPath currentbap = refsourceandtrgtnodeid[blocksl].SourceAccessPath;
				int blockel = refsourceandtrgtnodeid.FindIndex(blocksl, (TargetLocationAndPathPair ee) => ee.SourceAccessPath != currentbap);
				if(blockel == -1)
					blockel = refsourceandtrgtnodeid.Count;

				//if there is only 1 entry for the given access path then we don't need to do anything, so just skip all this
				if(blocksl + 1 < blockel)
				{
					for(int i = blocksl; i < blockel; ++i)
					{
						//we build up our partitions here and then add them to the output list at the end
						AMemPartEqClass parti = this.m_locToClassMap[refsourceandtrgtnodeid[i].TargetNode];

						for(int j = blocksl; j < blockel; ++j)
						{
							AMemPartEqClass partj = this.m_locToClassMap[refsourceandtrgtnodeid[j].TargetNode];

							if(parti == partj)
								continue;

							bool ispredequiv = AMemPartEqClass.CheckEquivPartitionsPredEquiv(parti, partj, ignoreidentitystate);
							if(ispredequiv)
							{
								succproc = true;
								this.MergeEqClasses(parti, partj);
							}
						}
					}
				}

				blocksl = blockel;
			}

			return succproc;
		}

		/// <summary>
		/// Using <c>src</c> as the root add all the successor nodes to the processing list.
		/// </summary>
		private void AddSuccssorsAsNeeded(AMemPartEqClass src, Queue<AMemPartEqClass> toproc)
		{
			Contract.Requires(src != null);
			Contract.Requires(toproc != null);

			for(int i = 0; i < src.PartitionElems.Count; ++i)
			{
				ALocation ll = src.PartitionElems[i];
				IEnumerator<ATrgtEnum> trgtenum = ll.GetTargetEnum();
				while(trgtenum.MoveNext())
				{
					ATrgtEnum tte = trgtenum.Current;
					ALocation qqtn = this.LookupTargetLocation(ll, tte.TrgtAddress);
					AMemPartEqClass qqclass = this.m_locToClassMap[qqtn];
					if(qqclass.Color == AMemPartEqClass.VisitColor.White)
					{
						qqclass.Color = AMemPartEqClass.VisitColor.Black;
						toproc.Enqueue(qqclass);
					}
				}
			}
		}

		/////////////////////////////////////////////////////////
		//traversal support

		/// <summary>
		/// Sort the graph psudo-topologically put the results into sorted (also computing the visited info into vinfo).
		/// </summary>
		private void TopoSort(List<AMemPartEqClass> sorted, List<ALocation> domroots)
		{
			Contract.Requires(sorted != null && sorted.Count == 0);

			HashSet<AMemPartEqClass> roots = new HashSet<AMemPartEqClass>();
			for(int i = 0; i < domroots.Count; ++i)
				roots.Add(this.m_locToClassMap[domroots[i]]);

			foreach(AMemPartEqClass eqc in roots)
				this.DoDFSVisit(eqc, sorted);

			sorted.Reverse();
		}

		private void DoDFSVisit(AMemPartEqClass eqc, List<AMemPartEqClass> revsortedlist)
		{
			Contract.Requires(eqc != null);
			Contract.Requires(revsortedlist != null);

			if(eqc.Color != AMemPartEqClass.VisitColor.White)
				return;

			eqc.Color = AMemPartEqClass.VisitColor.Grey;
			for(int k = 0; k < eqc.PartitionElems.Count; ++k)
			{
				ALocation sl = eqc.PartitionElems[k];
				IEnumerator<ATrgtEnum> trgtenum = sl.GetTargetEnum();
				while(trgtenum.MoveNext())
				{
					ATrgtEnum tte = trgtenum.Current;
					ALocation trgtl = this.LookupTargetLocation(sl, tte.TrgtAddress);
					AMemPartEqClass assoccl = this.m_locToClassMap[trgtl];
					this.DoDFSVisit(assoccl, revsortedlist);
				}
			}

			eqc.Color = AMemPartEqClass.VisitColor.Black;
			revsortedlist.Add(eqc);
		}
	}

	internal class AMemPartEqClass
	{
		internal enum VisitColor : byte { White = 0x0, Grey = 0x1, Black = 0x2, Dead = 0x3 };

		/// <summary>
		/// For traversal processing.
		/// </summary>
		internal VisitColor Color;

		/// <summary>
		/// An integer identifier that for this equivalence class.
		/// </summary>
		private readonly int m_partitionID;

		//////////////////////////////////////////
		//Info on the properties of the nodes represented by this partition.

		/// <summary>
		/// All types for the locations in this set (AS A SORTED LIST).
		/// </summary>
		private readonly List<IRType> m_allTypes;

		/// <summary>
		/// All ids for the locations in this set (AS A SORTED LIST).
		/// </summary>
		private readonly List<int> m_allIDS;

		/// <summary>
		/// All escape info for the locations in this set (AS A SORTED LIST).
		/// </summary>
		private readonly List<EscapeInfoStub> m_allEsc;

		/// <summary>
		/// All of the locations that make up this class.
		/// </summary>
		private readonly List<ALocation> m_partitionElems;

		//////////////////////////////////////////
		//Info on the successors and predecessors.

		/// <summary>
		/// Set of all general memory partitions which have references to this one.
		/// THIS DOES NOT INCLUDE NAMED MEMORY LOCATIONS (e.g. that are the home locations of variables or stack locations).
		/// </summary>
		private readonly HashSet<InRefIDAndPathPair> m_predMemoryPartitions;

		/// <summary>
		/// If a location in this partition is the target of a name binding (i.e., this is the home location of a variable on the stack) 
		/// then this is the name of that variable.
		/// </summary>
		private IRRootIdentifier m_nameBindingPredecssor;

		/// <summary>
		/// List (SORTED) of all the FULLYRESOLVED external references that refer to a location in this partition.
		/// </summary>
		private List<AExternalRef> m_extPred;

		/// <summary>
		/// List (SORTED) of all root named storage locations with references to this (i.e., stack locations that are 
		/// variable or static home locations).
		/// </summary>
		private List<IRCompareableName> m_varLocPred;

		/// <summary>
		/// List (SORTED) of all stack locations (and offsets) with references to this.
		/// </summary>
		private List<StackLocAndAccessPathPair> m_stackLocPred;

		/// <summary>
		/// Initialize the given equivalence class with a single node.
		/// </summary>
		internal AMemPartEqClass(int partid, ALocation initloc)
		{
			Contract.Requires(initloc != null);

			this.Color = VisitColor.White;

			this.m_partitionID = partid;

			this.m_allTypes = new List<IRType>();
			this.m_allTypes.Add(initloc.LocationType);

			this.m_allIDS = new List<int>(initloc.IdentityTags);

			this.m_allEsc = new List<EscapeInfoStub>(initloc.AllocationEscapeSites.Length);
			for(int i = 0; i < initloc.AllocationEscapeSites.Length; ++i)
				this.m_allEsc.Add(new EscapeInfoStub(initloc.AllocationEscapeSites[i].EscapeLine, initloc.AllocationEscapeSites[i].EscapeLoopFlow));
			this.m_allEsc.Sort();

			this.m_partitionElems = new List<ALocation>();
			this.m_partitionElems.Add(initloc);

			////
			this.m_predMemoryPartitions = new HashSet<InRefIDAndPathPair>();

			this.m_nameBindingPredecssor = null;
			this.m_extPred = null;
			this.m_varLocPred = null;
			this.m_stackLocPred = null;
		}

		/// <summary>
		/// Set this partition as containing the home location for a variable or static field.
		/// </summary>
		internal void SetAsNameHomeLocation(IRRootIdentifier r)
		{
			Contract.Requires(r != null);
			Contract.Assert(this.m_nameBindingPredecssor == null);

			this.m_nameBindingPredecssor = r;
		}

		/// <summary>
		/// Set this partition as containing a node that is the target of an external reference.
		/// </summary>
		internal void AddAsTargetOfExternalRef(AExternalRef eref)
		{
			Contract.Requires(eref != null);

			if(this.m_extPred == null)
				this.m_extPred = new List<AExternalRef>();

			int pos = this.m_extPred.BinarySearch(eref);
			if(pos < 0)
				this.m_extPred.Insert(~pos, eref);
		}

		/// <summary>
		/// Set this partition as containing a node that is the target of a variable or static field.
		/// </summary>
		internal void AddAsTargetOfVarOrStatic(IRRootIdentifier r)
		{
			Contract.Requires(r != null);

			if(this.m_varLocPred == null)
				this.m_varLocPred = new List<IRCompareableName>();

			int pos = this.m_varLocPred.BinarySearch((IRCompareableName)r);
			if(pos < 0)
				this.m_varLocPred.Insert(~pos, (IRCompareableName)r);
		}

		/// <summary>
		/// Set this partition as containing a node that is the target of an eval stack location.
		/// </summary>
		internal void AddAsTargetOfStackLoc(int spos, IRBasicAccessPath accp)
		{
			Contract.Requires(accp != null);

			if(this.m_stackLocPred == null)
				this.m_stackLocPred = new List<StackLocAndAccessPathPair>();

			StackLocAndAccessPathPair sap = new StackLocAndAccessPathPair(spos, accp);
			int pos = this.m_stackLocPred.BinarySearch(sap);
			if(pos < 0)
				this.m_stackLocPred.Insert(~pos, sap);
		}

		/// <summary>
		/// Set this partition as being the target of a general memory location from a node in the given partition.
		/// </summary>
		internal void AddMemoryPredecessor(int predpart, IRBasicAccessPath pth)
		{
			Contract.Requires(this.PartitionID != predpart);
			Contract.Requires(pth != null);

			InRefIDAndPathPair sap = new InRefIDAndPathPair(pth, predpart);
			this.m_predMemoryPartitions.Add(sap);
		}

		/// <summary>
		/// Merge the other equivalence class into this, destory other.
		/// </summary>
		internal void MergeOtherClassIntoThis(AMemPartEqClass other)
		{
			Contract.Requires(this != other);
			Contract.Requires(other != null);

			int alltsc = this.m_allTypes.Count;
			for(int i = 0; i < other.m_allTypes.Count; ++i)
			{
				int pos = this.m_allTypes.BinarySearch(0, alltsc, other.m_allTypes[i], null);
				if(pos < 0)
					this.m_allTypes.Add(other.m_allTypes[i]);
			}

			if(alltsc != this.m_allTypes.Count)
				this.m_allTypes.Sort();

			int allidc = this.m_allIDS.Count;
			for(int i = 0; i < other.m_allIDS.Count; ++i)
			{
				int pos = this.m_allIDS.BinarySearch(0, allidc, other.m_allIDS[i], null);
				if(pos < 0)
					this.m_allIDS.Add(other.m_allIDS[i]);
			}

			if(allidc != this.m_allIDS.Count)
				this.m_allIDS.Sort();

			int allescc = this.m_allEsc.Count;
			for(int i = 0; i < other.m_allEsc.Count; ++i)
			{
				int pos = this.m_allEsc.BinarySearch(0, allescc, other.m_allEsc[i], null);
				if(pos < 0)
					this.m_allEsc.Add(other.m_allEsc[i]);
			}

			if(allescc != this.m_allEsc.Count)
				this.m_allEsc.Sort();

			this.m_partitionElems.AddRange(other.m_partitionElems);

			////
			this.m_predMemoryPartitions.UnionWith(other.m_predMemoryPartitions);
			this.m_predMemoryPartitions.RemoveWhere((InRefIDAndPathPair iirp) => iirp.SourcePartition == this.m_partitionID);

			Contract.Assert((this.m_nameBindingPredecssor == other.m_nameBindingPredecssor) | ((this.m_nameBindingPredecssor == null) & (other.m_nameBindingPredecssor == null)), "Should not be mangling name bindings like this");

			////
			if((this.m_extPred != null) & (other.m_extPred != null))
			{
				for(int i = 0; i < other.m_extPred.Count; ++i)
				{
					int pos = this.m_extPred.BinarySearch(other.m_extPred[i]);
					if(pos < 0)
						this.m_extPred.Insert(~pos, other.m_extPred[i]);
				}
			}
			else if(this.m_extPred == null)
			{
				this.m_extPred = other.m_extPred;
			}
			else
			{ ;}

			if((this.m_varLocPred != null) & (other.m_varLocPred != null))
			{
				for(int i = 0; i < other.m_varLocPred.Count; ++i)
				{
					int pos = this.m_varLocPred.BinarySearch(other.m_varLocPred[i]);
					if(pos < 0)
						this.m_varLocPred.Insert(~pos, other.m_varLocPred[i]);
				}
			}
			else if(this.m_varLocPred == null)
			{
				this.m_varLocPred = other.m_varLocPred;
			}
			else
			{ ;}

			if((this.m_stackLocPred != null) & (other.m_stackLocPred != null))
			{
				for(int i = 0; i < other.m_stackLocPred.Count; ++i)
				{
					int pos = this.m_stackLocPred.BinarySearch(other.m_stackLocPred[i]);
					if(pos < 0)
						this.m_stackLocPred.Insert(~pos, other.m_stackLocPred[i]);
				}
			}
			else if(this.m_stackLocPred == null)
			{
				this.m_stackLocPred = other.m_stackLocPred;
			}
			else
			{ ;}
		}

		/// <summary>
		/// When we merge nodes we need to look at all successors and update their predecessor info.
		/// </summary>
		internal void UpdatePredInfoOnMerge(int oldpred, int newpred)
		{
			List<InRefIDAndPathPair> prem = new List<InRefIDAndPathPair>();
			List<InRefIDAndPathPair> padd = new List<InRefIDAndPathPair>();

			foreach(InRefIDAndPathPair pp in this.m_predMemoryPartitions)
			{
				if(pp.SourcePartition == oldpred)
				{
					prem.Add(pp);
					padd.Add(new InRefIDAndPathPair(pp.SourceAccessPath, newpred));
				}
			}

			for(int i = 0; i < prem.Count; ++i)
				this.m_predMemoryPartitions.Remove(prem[i]);

			this.m_predMemoryPartitions.UnionWith(padd);
		}

		/// <summary>
		/// Return true if we should merge these partitions based on being recursive (assuming that we already know they have an edge between them).
		/// </summary>
		public static bool CheckEquivPartitionsRecEquiv(AMemPartEqClass p1, AMemPartEqClass p2)
		{
			//make sure we don't mangle home locations for local vars/static fields
			if((p1.m_nameBindingPredecssor != null) | (p2.m_nameBindingPredecssor != null))
				return false;

			return IRProgram.AnyTypesInSetsRecursive(p1.m_allTypes, p2.m_allTypes);
		}

		/// <summary>
		/// Return true if we should merge these partitions based on predecessor equiv (assuming that we already know they have a common predecessor).
		/// </summary>
		[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity")]
		internal static bool CheckEquivPartitionsPredEquiv(AMemPartEqClass p1, AMemPartEqClass p2, bool ignoreidentitystate)
		{
			Contract.Requires(p1 != null);
			Contract.Requires(p2 != null);
			Contract.Requires(p1 != p2);

			//never mangle name bindings
			if((p1.m_nameBindingPredecssor != p2.m_nameBindingPredecssor) | (p1.IsHomeLocation != p2.IsHomeLocation))
				return false;

			//check if type overlap is satisfied
			bool typesoverlap = ListsOverlap<IRType>(p1.m_allTypes, p2.m_allTypes);
			if(!typesoverlap)
				return false;

			if(ignoreidentitystate)
			{
				//always make sure the sets of references from external statics are the same
				if((p1.m_extPred != null) | (p2.m_extPred != null))
				{
					bool p1hasstatic = (p1.m_extPred != null) && p1.m_extPred.Exists((AExternalRef aer) => aer.StaticRef != null);
					bool p2hasstatic = (p2.m_extPred != null) && p2.m_extPred.Exists((AExternalRef aer) => aer.StaticRef != null);

					if(p1hasstatic | p2hasstatic)
					{
						if(p1hasstatic & p2hasstatic)
						{
							//if there is any overlap in the statics
							for(int i = 0; i < p1.m_extPred.Count; ++i)
							{
								if(p1.m_extPred[i].StaticRef != null && p2.m_extPred.Exists((AExternalRef aer) => aer.StaticRef == p1.m_extPred[i].StaticRef))
									return true;
							}
						}

						return false;
					}
				}

				return true;
			}

			bool bothfixed = p1.IsHomeLocation & p2.IsHomeLocation;
			if(bothfixed)
				return ListsEqual<int>(p1.m_allIDS, p2.m_allIDS);
			else
			{
				bool alloccompat = ((p1.m_allEsc.Count != 0) & (p2.m_allEsc.Count != 0)) && ListsOverlap<EscapeInfoStub>(p1.m_allEsc, p2.m_allEsc);
				bool nonemptybutoverlap = ((p1.m_allIDS.Count != 0) & (p2.m_allIDS.Count != 0)) && ListsOverlap<int>(p1.m_allIDS, p2.m_allIDS);
				bool overlapidentitystate = (alloccompat | nonemptybutoverlap);

				if(!overlapidentitystate)
				{
					bool extrefsok = ((p1.m_extPred == null) & (p2.m_extPred == null)) || (((p1.m_extPred != null) & (p2.m_extPred != null)) && ListsEqual<AExternalRef>(p1.m_extPred, p2.m_extPred));
					if(!extrefsok)
						return false;

					//if we have the different identity states then we are pretty strict
					bool okvarpred = ((p1.m_varLocPred == null) & (p2.m_varLocPred == null)) || (((p1.m_varLocPred != null) & (p2.m_varLocPred != null)) && ListsEqual<IRCompareableName>(p1.m_varLocPred, p2.m_varLocPred));
					bool okstackpred = ((p1.m_stackLocPred == null) & (p2.m_stackLocPred == null)) || (((p1.m_stackLocPred != null) & (p2.m_stackLocPred != null)) && ListsEqual<StackLocAndAccessPathPair>(p1.m_stackLocPred, p2.m_stackLocPred));
					bool oksfequiv = (okvarpred & okstackpred);
					if(!oksfequiv)
						return false;

					bool okhequiv = ((p1.m_predMemoryPartitions.Count == 0) & (p2.m_predMemoryPartitions.Count == 0)) || p1.m_predMemoryPartitions.Overlaps(p2.m_predMemoryPartitions);
					return okhequiv;
				}
				else
				{
					bool extrefsok = ((p1.m_extPred == null) | (p2.m_extPred == null)) || ListsOverlap<AExternalRef>(p1.m_extPred, p2.m_extPred);
					if(!extrefsok)
						return false;

					//if identity states overlap then we are less strict
					bool okvarpred = ((p1.m_varLocPred == null) | (p2.m_varLocPred == null)) || ListsOverlap<IRCompareableName>(p1.m_varLocPred, p2.m_varLocPred);
					bool okstackpred = ((p1.m_stackLocPred == null) | (p2.m_stackLocPred == null)) || ListsOverlap<StackLocAndAccessPathPair>(p1.m_stackLocPred, p2.m_stackLocPred);
					bool svpredeq = (okvarpred & okstackpred);
					if(!svpredeq)
						return false;

					bool hpredeq = ((p1.m_predMemoryPartitions.Count == 0) | (p2.m_predMemoryPartitions.Count == 0)) || p1.m_predMemoryPartitions.Overlaps(p2.m_predMemoryPartitions);
					return hpredeq;
				}
			}
		}

		/// <summary>
		/// Return true if the two unique sorted lists overlap.
		/// </summary>
		private static bool ListsOverlap<T>(List<T> l1, List<T> l2) where T : IComparable<T>
		{
			T v1, v2;
			int index1 = 0;
			int index2 = 0;
			while((index1 < l1.Count) & (index2 < l2.Count))
			{
				v1 = l1[index1];
				v2 = l2[index2];

				int cpv = v1.CompareTo(v2);
				if(cpv == 0)
					return true;
				else if(cpv < 0)
					++index1;
				else
					++index2;
			}

			return false;
		}

		/// <summary>
		/// Return true if the two unique sorted lists are equal.
		/// </summary>
		private static bool ListsEqual<T>(List<T> l1, List<T> l2) where T : IComparable<T>
		{
			if(l1.Count != l2.Count)
				return false;

			for(int i = 0; i < l1.Count; ++i)
			{
				if(l1[i].CompareTo(l2[i]) != 0)
					return false;
			}

			return true;
		}

		////

		internal int PartitionID { get { return this.m_partitionID; } }

		internal List<IRType> PartitionTypes { get { return this.m_allTypes; } }

		internal bool IsHomeLocation { get { return this.m_nameBindingPredecssor != null; } }

		internal List<ALocation> PartitionElems { get { return this.m_partitionElems; } }
	}

	/// <summary>
	/// This is a simple struct that represents parts of the escape info that is relevant for computing the equivalence classes.
	/// </summary>
	internal struct EscapeInfoStub : IComparable<EscapeInfoStub>, IEquatable<EscapeInfoStub>
	{
		/// <summary>
		/// This is the most recent escape, or alloction site associated with this object.
		/// </summary>
		internal readonly int EscLine;

		/// <summary>
		/// This tracks the flow time of the alloc/escape in terms of loop current/previous iterations -- initially set to the line
		/// </summary>
		internal readonly int EscFlowLoop;

		internal EscapeInfoStub(int escline, int escloop)
		{
			this.EscLine = escline;
			this.EscFlowLoop = escloop;
		}

		public static bool operator ==(EscapeInfoStub eis1, EscapeInfoStub eis2)
		{ return eis1.Equals(eis2); }

		public static bool operator !=(EscapeInfoStub eis1, EscapeInfoStub eis2)
		{ return !eis1.Equals(eis2); }

		public static bool operator <(EscapeInfoStub eis1, EscapeInfoStub eis2)
		{ return eis1.CompareTo(eis2) < 0; }

		public static bool operator >(EscapeInfoStub eis1, EscapeInfoStub eis2)
		{ return eis1.CompareTo(eis2) > 0; }

		public override int GetHashCode()
		{ return this.EscFlowLoop ^ this.EscLine; }

		public override bool Equals(Object obj)
		{ return (obj is EscapeInfoStub) && this.Equals((EscapeInfoStub)obj); }

		public int CompareTo(EscapeInfoStub other)
		{
			int esclf = (this.EscFlowLoop - other.EscFlowLoop);
			return (esclf != 0 ? esclf : this.EscLine - other.EscLine);
		}

		public bool Equals(EscapeInfoStub other)
		{ return (this.EscLine == other.EscLine) & (this.EscFlowLoop == other.EscFlowLoop); }

	}

	/// <summary>
	/// A simple structure to use in computing the congruence closure information. Tracks target equivalence class and the source access path for the reference to 
	/// this equivalence class in some structure.
	/// </summary>
	internal struct InRefIDAndPathPair : IComparable<InRefIDAndPathPair>, IEquatable<InRefIDAndPathPair>
	{
		internal readonly IRBasicAccessPath SourceAccessPath;

		internal readonly int SourcePartition;

		internal InRefIDAndPathPair(IRBasicAccessPath pth, int spart)
		{
			this.SourceAccessPath = pth;
			this.SourcePartition = spart;
		}

		public static bool operator ==(InRefIDAndPathPair slpt1, InRefIDAndPathPair sltp2)
		{ return slpt1.Equals(sltp2); }

		public static bool operator !=(InRefIDAndPathPair slpt1, InRefIDAndPathPair sltp2)
		{ return !slpt1.Equals(sltp2); }

		public static bool operator <(InRefIDAndPathPair slpt1, InRefIDAndPathPair sltp2)
		{ return slpt1.CompareTo(sltp2) < 0; }

		public static bool operator >(InRefIDAndPathPair slpt1, InRefIDAndPathPair sltp2)
		{ return slpt1.CompareTo(sltp2) > 0; }

		public override int GetHashCode()
		{ return (this.SourceAccessPath.GetHashCode()) ^ this.SourcePartition; }

		public override bool Equals(Object obj)
		{ return (obj is InRefIDAndPathPair) && this.Equals((InRefIDAndPathPair)obj); }

		public int CompareTo(InRefIDAndPathPair other)
		{
			int accpcmp = (other.SourcePartition - this.SourcePartition);
			return (accpcmp != 0 ? accpcmp : this.SourceAccessPath.CompareTo(other.SourceAccessPath));
		}

		public bool Equals(InRefIDAndPathPair other)
		{ return (this.SourceAccessPath == other.SourceAccessPath) & (this.SourcePartition == other.SourcePartition); }
	}

	/// <summary>
	/// A simple structure to use in computing the congruence closure information. Tracks stack position and access path for a predecessor location.
	/// </summary>
	internal struct StackLocAndAccessPathPair : IComparable<StackLocAndAccessPathPair>, IEquatable<StackLocAndAccessPathPair>
	{
		internal readonly int StackPos;

		internal readonly IRBasicAccessPath SourceAccessPath;

		internal StackLocAndAccessPathPair(int spos, IRBasicAccessPath pth)
		{
			this.StackPos = spos;
			this.SourceAccessPath = pth;
		}

		public static bool operator ==(StackLocAndAccessPathPair slpt1, StackLocAndAccessPathPair sltp2)
		{ return slpt1.Equals(sltp2); }

		public static bool operator !=(StackLocAndAccessPathPair slpt1, StackLocAndAccessPathPair sltp2)
		{ return !slpt1.Equals(sltp2); }

		public static bool operator <(StackLocAndAccessPathPair slpt1, StackLocAndAccessPathPair sltp2)
		{ return slpt1.CompareTo(sltp2) < 0; }

		public static bool operator >(StackLocAndAccessPathPair slpt1, StackLocAndAccessPathPair sltp2)
		{ return slpt1.CompareTo(sltp2) > 0; }

		public override int GetHashCode()
		{ return (this.SourceAccessPath.GetHashCode()) ^ this.StackPos; }

		public override bool Equals(Object obj)
		{ return (obj is StackLocAndAccessPathPair) && this.Equals((StackLocAndAccessPathPair)obj); }

		public int CompareTo(StackLocAndAccessPathPair other)
		{
			int accpcmp = (other.StackPos - this.StackPos);
			return (accpcmp != 0 ? accpcmp : this.SourceAccessPath.CompareTo(other.SourceAccessPath));
		}

		public bool Equals(StackLocAndAccessPathPair other)
		{ return (this.SourceAccessPath == other.SourceAccessPath) & (this.StackPos == other.StackPos); }
	}

	/// <summary>
	/// A simple structure to use in computing the congruence closure information. A simple access path and target node pair.
	/// </summary>
	internal struct TargetLocationAndPathPair : IComparable<TargetLocationAndPathPair>, IEquatable<TargetLocationAndPathPair>
	{
		internal readonly IRBasicAccessPath SourceAccessPath;

		internal readonly ALocation TargetNode;

		internal TargetLocationAndPathPair(IRBasicAccessPath pth, ALocation tl)
		{
			this.SourceAccessPath = pth;
			this.TargetNode = tl;
		}

		public static bool operator ==(TargetLocationAndPathPair slpt1, TargetLocationAndPathPair sltp2)
		{ return slpt1.Equals(sltp2); }

		public static bool operator !=(TargetLocationAndPathPair slpt1, TargetLocationAndPathPair sltp2)
		{ return !slpt1.Equals(sltp2); }

		public static bool operator <(TargetLocationAndPathPair slpt1, TargetLocationAndPathPair sltp2)
		{ return slpt1.CompareTo(sltp2) < 0; }

		public static bool operator >(TargetLocationAndPathPair slpt1, TargetLocationAndPathPair sltp2)
		{ return slpt1.CompareTo(sltp2) > 0; }

		public override int GetHashCode()
		{ return (this.SourceAccessPath.GetHashCode()) ^ this.TargetNode.Address; }

		public override bool Equals(Object obj)
		{ return (obj is TargetLocationAndPathPair) && this.Equals((TargetLocationAndPathPair)obj); }

		public int CompareTo(TargetLocationAndPathPair other)
		{
			int accpcmp = this.SourceAccessPath.CompareTo(other.SourceAccessPath);
			return (accpcmp != 0 ? accpcmp : (other.TargetNode.Address - this.TargetNode.Address));
		}

		public bool Equals(TargetLocationAndPathPair other)
		{ return (this.SourceAccessPath == other.SourceAccessPath) & (this.TargetNode == other.TargetNode); }
	}
}
